package com.sali.DP;

/**
 * 有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
 * <p>
 * 现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
 * <p>
 * 求所能获得硬币的最大数量。
 */
public class LeetCode_312 {


    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] newNums = new int[n + 2];
        newNums[0] = 1;
        newNums[n + 1] = 1;
        System.arraycopy(nums, 0, newNums, 1, n); // 预处理：添加虚拟边界

        int[][] dp = new int[n + 2][n + 2]; // dp[left][right]表示戳破(left, right)间气球的最大硬币数

        // 外层循环：控制区间长度（gap为区间长度-1）
        for (int gap = 2; gap < newNums.length; gap++) {
            // 内层循环：枚举所有可能的左端点left
            for (int left = 0; left < newNums.length - gap; left++) {
                int right = left + gap; // 右端点 = 左端点 + 区间长度
                int max = 0;
                // 枚举(left, right)间最后一个被戳破的气球i
                for (int i = left + 1; i < right; i++) {
                    // 计算当前i作为最后一个气球时的硬币和，取最大值
                    max = Math.max(max, dp[left][i] + dp[i][right] + newNums[left] * newNums[i] * newNums[right]);
                }
                dp[left][right] = max; // 记录(left, right)区间的最大硬币数
            }
        }

        return dp[0][n + 1]; // 返回整个区间（0到n+1）的最大硬币数
    }

}
